﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0083_GenerateParenthesis : IAlgorithm
    {
        // 22. 括号生成

        // 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

        // 提示：
        //  1 <= n <= 8

        public void Test()
        {
            // 算法参数定义
            var n = 3;
            // 算法执行与打印
            foreach (var item in GenerateParenthesis(n))
            {
                Console.Write(item + " ");
            }
        }

        // 算法
        // 1 => ["(",")"]
        // 2 => ["(","()",")"]
        // 3 => ["(","(())",")"]
        public IList<string> GenerateParenthesis(int n)
        {
            var ans = new List<string>();
            Backtrack(ans, new StringBuilder(), 0, 0, n);
            return ans;
        }
        public void Backtrack(List<string> ans, StringBuilder cur, int open, int close, int max)
        {
            if (cur.Length == max * 2)
            {
                ans.Add(cur.ToString());
                return;
            }
            if (open < max)
            {
                cur.Append('(');
                Backtrack(ans, cur, open + 1, close, max);
                cur.Remove(cur.Length - 1,1);
            }
            if (close < open)
            {
                cur.Append(')');
                Backtrack(ans, cur, open, close + 1, max);
                cur.Remove(cur.Length - 1, 1);
            }
        }
    }
}
